package algorithms.concCBJ;

import java.util.GregorianCalendar;
import java.util.TreeMap;
import java.util.Vector;

import algorithms.TwoIntegers;

import ordering.VariableOrdering;
import priorities.PriorityManager;


import general.Agent;
import general.ChannelAgent;
import general.NotImplementedException;
import general.CPA.CPA;
import general.conflictset.ConflictSet;
import general.constraints.VariableConstraints;
import general.currentdomain.ArrayCurrentDomain;
import general.currentdomain.CurrentDomain;
import general.messages.BacktrackMessage;
import general.messages.CPAMessage;
import general.messages.ConflictMessage;
import general.messages.FailMessage;
import general.messages.Message;
import general.messages.RestoreMessage;
import general.messages.SplitMessage;
import general.messages.SuccessMessage;

/**
 *	Concurrent Backtracking Agent - main class for the ConcBT algorithm
 */
public class ConcCBJAgent extends ChannelAgent implements Agent{

	private String solution;

	private int maxCPA;
	private byte domain;
	private int split_limit;
	private long startTime;
	private long numSPs;
	private long maxSPs;
	private double numSPsForAverage;
	private double numMoves;
	private double concurrency;
	private int curSPs;
	private TreeMap<TwoIntegers, CBJSearchProcess> sps;
	private VariableOrdering ordering;

	private Vector<Integer> spGraph;

	/**
	 * Creates an instance of ConcBTAgent
	 * @param id id of this agent
	 * @param n total number of agents
	 * @param domain domain size of this agent
	 * @param split_limit number of steps to do before splitting a CPA
	 * @param constraints constraints for this agent
	 * @param ordering ordering heuristics for this agent
	 * @param protoCpa a prototype CPA to create new CPA's
	 */
	public ConcCBJAgent(byte id, byte n, byte domain, int split_limit, VariableConstraints constraints, VariableOrdering ordering, CPA protoCpa, int delay) {
		super(id, n, constraints, protoCpa, delay);
		this.sps = new TreeMap<TwoIntegers, CBJSearchProcess>();
		this.domain = domain;
		this.maxCPA = 0;
		this.split_limit = split_limit;
		this.ordering = ordering;

		this.numSPsForAverage = 0;
		this.numSPs = 0;
		this.maxSPs = 0;
		this.curSPs = 0;
		this.numMoves = 0;
		this.concurrency = 0;

		this.spGraph = new Vector<Integer>();
	}

	@Override
	public void run() {
		startTime = GregorianCalendar.getInstance().getTimeInMillis();
		log("I'm running", LOG_STARTRUN);
		loop();
		long totalTime = GregorianCalendar.getInstance().getTimeInMillis() - startTime;
		log("Total runtime: " + (totalTime) +" miliseconds", LOG_FINISHRUN);
		for (int i=0; i<n; i++) if (i!=id){
			sendEndMessage(i);
		}

		while(numOpenChannels>0){
			readFromBuffer(true);
		}
		//		close();
	}

	/**
	 * Initializes the main SP for the first variable by creating a sp for the first variable and adding all of the other
	 * SPs to its split set(including itself)
	 * 
	 * a SP that has no parent, alwais contains an instance of itself in its split set
	 */
	private void initializeSPs(){
		log("Initializing SPs", LOG_INIT);
		CPA firstCpa = getNewCPA(n, maxCPA++, id);					//creates new CPA for the first variable
		CurrentDomain firstDm = new ArrayCurrentDomain(domain);		//creates a domain for the first variable
		for (byte j=1; j<domain; j++){							
			firstDm.remove(j);										//removes all of the values from the domain except 0
		}
		CBJSearchProcess firstsp = new CBJSearchProcess(firstCpa, domain, n, firstDm);	//creates the search process
		firstsp.setOrigin(firstsp);									//sets origin for the search process
		sps.put(firstsp.getId(), firstsp);							//insert the search process to the SP list
		numSPs++;
		curSPs++;
		assignCPA(firstCpa);
		for (int i=1; i<domain; i++){								//does the same for the reset of the SPs
			CPA p = getNewCPA(n, maxCPA++, id);				
			CurrentDomain dm = new ArrayCurrentDomain(domain);
			for (byte j=0; j<domain; j++) if (j!=i){		
				dm.remove(j);
			}
			CBJSearchProcess sp = new CBJSearchProcess(p, domain,n,  dm);
			sp.setOrigin(firstsp);
			sps.put(sp.getId(), sp);
			numSPs++;
			curSPs++;
			assignCPA(p);
		}
		maxSPs = Math.max(curSPs, maxSPs);
	}

	/**
	 * Handles a newly arrived CPA:
	 * if its unknown - creates a new search process
	 * if its known - update the CPA instance that is saved in this agent with the new one
	 * 
	 * if we are the creator of this CPA - we will reset the steps
	 * if not - we will check how many steps has this CPA done, and send a SPLIT message to its creator if needed 
	 * @param cpa
	 */
	private void receiveCPA(CPA cpa){
		if (sps.get(cpa.getId()) == null){			//unknown CPA
			log("Creating new SPs - " + cpa, LOG_CREATENEWSP);
			CBJSearchProcess sp = new CBJSearchProcess(cpa, domain, n, new ArrayCurrentDomain(domain));	//makes new SearchProcess and initializes it
			sp.setOrigin(sp);
			numSPs++;
			curSPs++;
			maxSPs = Math.max(curSPs, maxSPs);
			sps.put(sp.getId(), sp);
		} else {									//known CPA
			sps.get(cpa.getId()).updateCPA(cpa); 	//update known CPA with new one
			//TODO - might want to re-add the SP to its parent's split set ?
		}

		if (cpa.getCreator()==id){					//reset the steps in case we created this CPA
			cpa.resetSteps();
		} else {					
			cpa.addStep();							//increase step counter
			if (cpa.getSteps()>=split_limit){		//split the CPA if needed
				log("Creating a split - " + cpa, LOG_SPLIT);
				int splitter = cpa.getCreator();	//sends a split message to the CPA creator
				cpa.resetSteps();					//
				sendSplit(cpa.getId(), splitter);
			}
		}
	}

	/**
	 * assigns a value to a CPA and sends it to the next variable
	 * @param p the CPA to assign a value to
	 * @return True - if we succeeded or failed, so this agent will stop working, False - if we still need to continue
	 */
	private boolean assignCPA(CPA p){ //returns true if done
		boolean consistent = false;
		CBJSearchProcess sp = sps.get(p.getId());
		CurrentDomain current_domain = sp.getDomain();
		for (Integer i: current_domain){		//assigns a value - goes over all of the domain and checks for consistent assignments
			consistent = true;
			byte myVal = i.byteValue();
			//			System.out.println(Thread.currentThread().getName() + ", " + p);
			for (Integer j: p){					//checks for inconsistency with each of the already assigned value
				byte other = j.byteValue();
				byte otherVal = p.getValue(other);
				consistent = check(myVal, other, otherVal);
				if (!consistent){
					current_domain.remove(myVal);
					sp.addConflict(other);
					break;
				}
			}
			if (consistent){					//found a consistent assignment
				p.insert(id, myVal);
				current_domain.remove(myVal);
				break;
			}
		}
		if (consistent){										//3
			if (p.isFull()){					//got to a full assignment
				log("SUCCESS!!! - " + p.toString(), LOG_SUCCESS);
				solution = p.toString();
				success(p);
				return true;
			} else {							//partial assignment - moving CPA to the next agent(using the variable ordering heuristics)
				byte nextAgent = ordering.next(p, id, constraints);
				log("Sending CPA to next("+nextAgent+") - " + p, LOG_SENDNEXT);
				send(p, nextAgent);
				return false;				
			}
		} else {								//no consistent assignment, backtracking
			log("Backtracking" , LOG_BACKTRACK);
			return backtrack(p);
		}
	}

	/**
	 * Performs backtrack for a CPA
	 * Checks if this CPA split set is empty:
	 * Empty - sends a backtrack message with the CPA's ID to the last assigning agent in the CPA
	 * not Empty - Marks the CPA as a failed assignment, and waits for the other CPA's to return 
	 * (since they might return with a solution and therefore we don't need to backtrack yet)
	 * @param p the CPA we need to perform the backtrack for
	 * @return True - if the backtrack is failed and we need to stop, False - if the backtrack succeeds
	 */
	private boolean backtrack(CPA p){
		TwoIntegers cpaId = p.getId();
		CBJSearchProcess sp = sps.get(cpaId);
		CBJSearchProcess originSP = sp.getOriginSP();
//		System.out.println(sp.getConflicts());
		originSP.addConflicts(sp.getConflicts());
		originSP.remove(cpaId);					//removes the SP from the OriginiSP
		sps.remove(cpaId);
		curSPs--;
		if (originSP.noMoreSplits()){			//no SPs remaining in the origin SP - we can backtrack
			CPA originCPA = originSP.getCpa();
			byte maxConflicted = ordering.max(originCPA, id, originSP.getConflicts());

			if (ordering.isFirst(id) || maxConflicted==-1){			//we are the first agent - FAIL
				log("We failed!", LOG_FAIL);
				fail();
				return true;
			} else {							//backtrack
				byte cpaCreator = (byte)originCPA.getCreator();

				byte bt; 
				if (ordering.isBefore(originCPA, cpaCreator, maxConflicted)){
					bt = maxConflicted;
				} else {
					bt = cpaCreator;
				}

				ordering.removeBigger(originCPA, originSP.getConflicts(), id);
				log("Sending backtrack to " + bt + " for " + p, LOG_BACKTRACK);
				send(originSP.getConflicts(), originCPA, bt);
				return false;
			}
		} else {								//more splits - mark as a failed CPA
			log("Marked CPA as failed " + p, LOG_BACKTRACK);
			sp.markFail();
			return false;
		}
	}

	/**
	 * Sends a success message to all of the other agents when finding a good CPA
	 * @param p the CPA that found to solve the problem
	 */
	private void success(CPA p){
		for (byte i=0; i<n; i++) if (i!=id) {
			sendSuccess(p, i);
		}
	}

	/**
	 * Sends a fail message to all of the other agents when finding out we failed
	 */
	private void fail(){
		for (byte i=0; i<n; i++) if (i!=id) {
			sendFail(i);
		}
	}

	/**
	 * Main loop of the thread -initializes the SPs if we are the first agent
	 * and until we are done - receives messages and handles them 
	 */
	private void loop(){
		if (ordering.isFirst(id)){
			initializeSPs();
		}
		boolean done = false;
		while(!done){
			//			spGraph.add(curSPs);
			numSPsForAverage = numSPsForAverage*(numMoves/(numMoves+1))+(((double)curSPs)/(numMoves+1));
			//			numSPsForAverage+=curSPs;
			numMoves++;
			Message m = receive();
			done = m.handle(this);
			PriorityManager.getInstance().updatePriority(this);
		}
	}

	public long getNumSPs() {
		return numSPs;
	}

	public long getMaxSPs() {
		return maxSPs;
	}

	public double getAverageSPs(){
		return numSPsForAverage;
		//return (double)numSPsForAverage/(double)numMoves;
	}

	/**
	 * 
	 * @return the vector containing the number of SPs over time
	 */
	public Vector<Integer> getSpGraph(){
		return spGraph;
	}

	/**
	 * creates a new domain for splitting, takes a given domain and
	 * divides the values left equally between the original domain and the new domain
	 * @param dm the domain to split
	 * @return the new domain generated from the Splitting
	 */
	private CurrentDomain makeNewDomain(CurrentDomain dm){
		boolean hasVals = false;
		CurrentDomain dm2 = new ArrayCurrentDomain(domain);
		boolean newDm = true;
		for (byte i=0; i<domain; i++){
			if (dm.isInDomain(i)){
				if(newDm){
					hasVals = true;
					dm.remove(i);
					dm2.insert(i);
					newDm = !newDm;
				} else {
					dm2.remove(i);
					newDm = !newDm;
				}
			} else {
				dm2.remove(i);
			}
		}
		if (hasVals) return dm2; else return null;
	}

	/**
	 * Splits a search process 
	 * Creating a domain for it, duplicating the CPA
	 * Unassigning the variable from the new CPA, registering a new SP and assigning a value to the new SP 
	 * @param cpaId
	 * @return
	 */
	public boolean split(TwoIntegers cpaId){
		CBJSearchProcess sp = sps.get(cpaId);				//SP to split	
		if (sp!=null && !sp.isFailed()){				//SP isn't marked as failed or removed because of backtracking 
			CurrentDomain dm = sp.getDomain();			//original SP's domain
			CurrentDomain dm2 = makeNewDomain(dm);		//new SP's domain
			if (dm2!=null){								//there are variables to split
				CPA newCpa = sp.getCpa().duplicate(maxCPA++, id);	//duplicate the original CPA
				newCpa.remove(id);						//removes this variable's assignment from the duplicated CPA
				CBJSearchProcess newSP = new CBJSearchProcess(newCpa, domain, n, dm2);	//create new search process
				newSP.setOrigin(sp.getOriginSP());		//adds the newSP to the split set and sets the originSP
				numSPs++;
				curSPs++;
				maxSPs = Math.max(curSPs, maxSPs);
				sps.put(newSP.getId(), newSP);
				assignCPA(newCpa);						//assigns a value to the new CPA
			} else if (ordering.hasNext(sp.getCpa(), id)) {	//no availiable variables for splitting - moves the split to the next variable
				sendSplit(sp.getId(), ordering.next(sp.getCpa(), id, constraints));
			}
		}
		return false;
	}

	private void updateConcurrency(TwoIntegers id, Message m) {
		Integer count = messageStatus.remove(id);
		if (count>0){
			messageStatus.put(id, count.intValue()-1);
		}
		double wait = waitTimes.get(m);
		//		System.out.println(wait + ", " + curSPs);
		concurrency = concurrency*((numMoves-1)/(numMoves))+((curSPs/wait)/(numMoves));
		//		System.out.println(concurrency);
	}


	@Override
	public boolean handleMessage(CPAMessage message) {
		CPA cpa = message.getCPA();
		updateConcurrency(cpa.getId(), message);
		log("Handling CPA - " + cpa, LOG_HANDLE_CPA);
		receiveCPA(cpa);
		sps.get(cpa.getId()).resetDomain();
		return assignCPA(cpa);
	}

	@Override
	public boolean handleMessage(BacktrackMessage message) {
		new NotImplementedException("ConcCBJAgent does not support BacktrackMessage").printStackTrace();
		return true;
	}

	@Override
	public boolean handleMessage(SplitMessage message) {
		log("Handling Split " + message.getId(), LOG_HANDLE_SPLIT);
		updateConcurrency(message.getId(), message);
		return split(message.getId());
	}

	@Override
	public boolean handleMessage(ConflictMessage message) {
		TwoIntegers cpaId = message.getCpa();
		updateConcurrency(cpaId, message);
		CBJSearchProcess sp = sps.get(cpaId);
		if (sp != null){
			CPA cpa = sp.getCpa();
			receiveCPA(cpa);
			ConflictSet c = message.getConflicts();
			log("Handling Conflicts - " + cpa + ", " + c, LOG_HANDLE_BACKTRACK);
			if (c.isConflicting(id)){		//normal backtrack
				c.remove(id);
				sp.addConflicts(c);
				byte lastAssignment = cpa.getValue(id);
				CurrentDomain currenDomain = sps.get(cpaId).getDomain(); 
				currenDomain.remove(lastAssignment);
				cpa.remove(id);
				return assignCPA(cpa);
			} else {
				sp.addConflicts(c);
				backtrack(cpa);
				return false;
			}
		} else {
			log("Error, conflict message resulted in unknown SP - " + cpaId, true);
			return false;
		}
	}

	@Override
	public boolean handleMessage(RestoreMessage restoretMessage) {
		new NotImplementedException("ConcBTAgent does not support RestoreMessage").printStackTrace();
		return true;
	}

	@Override
	public boolean handleMessage(FailMessage failuretMessage) {
		log("Failure detected", LOG_HANDLE_FAIL);
		return true;
	}

	@Override
	public boolean handleMessage(SuccessMessage successMessage) {
		log("Success detected - " + successMessage.getResult(), LOG_HANDLE_SUCCESS);
		solution = successMessage.getResult();
		return true;
	}

	/**
	 * 
	 * @return the solution of the problem or null if there isnt one
	 */
	public String getSolution() {
		if (solution==null) return null;
		return solution;
	}

	//TODO
	public double getConcurrency() {
		return concurrency;
	}


	//	private void debug(String line, CPA cpa){
	////		System.out.println("Agent " + id + ": " + line +"\t"+ cpa +" - " + cpa.getOverallId());
	//	}
	//	
	//	private void debug2(String line, CPA cpa){
	////		System.out.println("Agent " + id + ": " + line +"\t"+ cpa +" - " + cpa.getOverallId());
	//	}

	//TODO 	Check that when we backtrack - we wait for other backtracks (should use a small unsolvable CPS for this - should be working)

	//when an agent finds out he has to backtrack, he needs to send the maximum conflicting agent a backtrack message, and his conflicts.
	//the backtrack has to go through the creator of the CPA, in order to eliminate all of the splits

	//when an agent sees that he needs to assign a CPA, he should eliminate all of the splits of that CPA, and continue as usual

	//the problem is that multiple agents can send a backtrack message for the same CPA, thats why it has to go through its creator, which will eliminate all of the other 

}
